/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.linkedlist;

/**
 * <p>
 * 合并两个有序的链表 递归+非递归方法
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月17日
 */
public class MergeTwoSortedLists {
    /**
     * 非递归方法
     * @param l1
     * @param l2
     * @return
     * @author towan
     * 2015年5月17日
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //特殊情况处理
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(l1!=null && l2!=null){//注意逻辑
            //第一个数比第二数小，节点为第一个
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            //继续向前
            cur = cur.next;
        }
        if(l2==null){
            cur.next = l1;
        }
        if(l1==null){
            cur.next = l2;
        }
        return dummy.next;
    }
    /**
     * 递归方法
     * @param l1
     * @param l2
     * @return
     * @author towan
     * 2015年5月17日
     */
    public static ListNode mergeTwoLists2(ListNode l1,ListNode l2){
        //特殊情况处理
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode mergeNode = null;
        if(l1.val<l2.val){
            mergeNode = l1;
            mergeNode.next = mergeTwoLists2(l1.next, l2);//注意赋值
        }else{
            mergeNode = l2;
            mergeNode.next = mergeTwoLists2(l1, l2.next);
        }
        return mergeNode;
    }
}
